/**
 * 剑指 Offer 39. 数组中出现次数超过一半的数字
 * https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
 */

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function majorityElement(nums) {
//   const map = new Map();
//   for (let i = 0; i < nums.length; i += 1) {
//     const count = (map.get(nums[i]) || 0) + 1;
//     if (count > nums.length / 2) {
//       return nums[i];
//     }
//     map.set(nums[i], count);
//   }
//   return nums[0];
// }

/**
 * 投票算法
 * @param {number[]} nums
 * @return {number}
 */
function majorityElement(nums) {
  let guess = nums[0];
  let count = 1;
  for (let i = 1; i < nums.length; i += 1) {
    if (nums[i] === guess) {
      count += 1;
    } else {
      // eslint-disable-next-line no-lonely-if
      if (count === 1) {
        guess = nums[i];
      } else {
        count -= 1;
      }
    }
  }
  return guess;
}

console.log(majorityElement([1, 2, 3, 2, 2, 2, 5, 4, 2]) === 2);
console.log(majorityElement([1]) === 1);
